A blocking quadruple (BQ) is a quadruple of vertices of a graph such that anytwo vertices of the quadruple either miss (have no neighbours on) some pathconnecting the remaining two vertices of the quadruple, or are connected bysome path missed by the remaining two vertices. This is akin to the notion ofasteroidal triple used in the classical characterization of interval graphs byLekkerkerker and Boland. We show that a circular-arc graph cannot have ablocking quadruple. We also observe that the absence of blocking quadruples isnot in general sufficient to guarantee that a graph is a circular-arc graph.Nonetheless, it can be shown to be sufficient for some special classes ofgraphs, such as those investigated by Bonomo et al. In this note, we focus onchordal graphs, and study the relationship between the structure of chordalgraphs and the presence/absence of blocking quadruples. Our contribution istwo-fold. Firstly, we provide a forbidden induced subgraph characterization ofchordal graphs without blocking quadruples. In particular, we observe that allthe forbidden subgraphs are variants of the subgraphs forbidden for intervalgraphs. Secondly, we show that the absence of blocking quadruples is sufficientto guarantee that a chordal graph with no independent set of size five is acircular-arc graph. In our proof we use a novel geometric approach,constructing a circular-arc representation by traversing around a carefullychosen clique tree.
展开▼
